先考虑所有格子均未涂色的情况。
因为格子的涂色只会影响一行一列,所以可以设 dp(i,j) 表示还需要涂 i 行 , j 列的期望步数。
1.涂色格所在行列均未染色,由 dp(i−1,j−1) 转移,概率为 ni×nj
2.涂色格所在行未染色,列已染色,由 $dp(i-1,j) $ 转移,概率为 ni×nn−j
3.涂色格所在列未染色,行已染色,由 $dp(i,j-1) $ 转移,概率为 nn−i×nj
4.涂色格所在行列均已染色,由 dp(i,j) 转移,概率为 nn−i×nn−j
综上得:
dp(i,j)=1+dp(i−1,j)∗n2i∗(n−j)+dp(i,j−1)∗n2(n−i)∗j+dp(i−1,j−1)∗n2i∗j+dp(i,j)∗n2(n−i)∗(n−j)
移项得:
dp(i,j)=1−n2(n−i)(n−j)1+dp(i−1,j)∗n2i∗(n−j)+dp(i,j−1)∗n2(n−i)∗j+dp(i−1,j−1)∗n2i∗j
上下同时乘 n2 得到:
dp(i,j)=n2−(n−i)(n−j)n2+dp(i−1,j)∗i∗(n−j)+dp(i,j−1)∗(n−i)∗j+dp(i−1,j−1)∗i∗j
边界条件:
1.dp[0][0]=0
2.dp[0][i]/dp[i][0]=∑j=1i⌊ji⌋ 经典的邮票收集问题。
现在再考虑一开始有涂色的格子,其实只是让其中一些行列提前满足要求,即答案并不是 dp(n,n) ,而是减去已满足数量的结果自己意会一下。
#include <cstdio>
const int MAXN = 2e3;
int n , m , x , y;
bool vis[ 2 ][ MAXN + 5 ];
double dp[ MAXN + 5 ][ MAXN + 5 ];
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
if( !vis[ 0 ][ u ] ) x -= ( vis[ 0 ][ u ] = 1 );
if( !vis[ 1 ][ v ] ) y -= ( vis[ 1 ][ v ] = 1 );
}
x += n , y += n;
dp[ 0 ][ 0 ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
dp[ i ][ 0 ] = dp[ i - 1 ][ 0 ] + n * 1.0 / i;
dp[ 0 ][ i ] = dp[ 0 ][ i - 1 ] + n * 1.0 / i;
}
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
dp[ i ][ j ] = ( n * n + dp[ i - 1 ][ j ] * i * ( n - j ) + dp[ i ][ j - 1 ] * ( n - i ) * j + dp[ i - 1 ][ j - 1 ] * i * j ) / ( n * n - ( n - i ) * ( n - j ) );
printf("%.10f", dp[ x ][ y ] );
return 0;
}